package com.lx.algorithm.temp;

/**
 * Description: 返回最大的价值
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-25 10:52:20
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-25     张李鑫                     1.0         1.0 Version
 */
public class Knapsack {
    /**
     * 用两个数组去标识 重量跟价值
     * 有一个最大重量的阈值
     * 返回在不超重的情况下最大的价值
     */
    public static int maxValue(int[] v, int[] w, int big) {

        return process(v, w, big, 0);
    }


    /**
     * <p>
     * 暴力递归
     * </p>
     *
     * @param v     价值数组
     * @param w     重量数组
     * @param big   剩余重量
     * @param index 当前索引
     * @return int
     * @Author zlx
     * @date 2021/10/28
     */
    public static int process(int[] v, int[] w, int big, int index) {
        if (big < 0) {
            return -1;
        }
        if (index == v.length) {
            return 0;
        }
        //拿跟不拿两个情况 如果拿的话 看下层的返回值是否为-1 如果为-1 说明当前选择是无效的
        int p1 = process(v, w, big - w[index], index + 1);
        if (p1 != -1) {
            p1 += v[index];
        }
        int p2 = process(v, w, big, index + 1);
        return Math.max(p1, p2);
    }


    /**
     * <p>
     *    动态规划
     * </p>
     * @param  v
     * @param  w
     * @param  big
     * @return int
     * @Author zlx
     * @date 2021/10/28
     */
    public static int dp(int[] v, int[] w, int big) {
        int[][] dp = new int[v.length + 1][big + 1];
        for (int i = v.length - 1; i >= 0; i--) {
            for (int i1 = 0; i1 < dp[i].length; i1++) {
                int p1 = dp[i + 1][i1];
                int p2 = 0;
                if (i1 - w[i] >= 0) {
                    p2 += v[i];
                    p2+=dp[i+1][i1-w[i]];
                }
                dp[i][i1] = Math.max(p1, p2);
            }
        }
        return dp[0][big];
    }


    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        System.out.println(dp(values, weights, 15));
        System.out.println(maxValue(values, weights, 15));
    }
}

